Many systems which rely on databases employ a keying scheme to aid in the searching of the database. Records in the database are stored in a somewhat random order and then an index is generated to link the database records into sequence based on a portion of the data. This portion is commonly referred to as the key.
In conventional data processing systems, the construction of the index and the accessing of the data based on the index file may require a number of processing steps. This method of storing and accessing data is not appropriate, therefore, in a real-time processing environment in which data must be processed quickly. In addition, for databases having relatively small records, the index file may be almost as large as the database itself.
In video scheduling, for example, a particular program schedule is likely to be built up a bit at a time, with the broadcast time of some programs being decided before the broadcast time of other programs, and with frequent changes in the lineup. This has the result that when the data relating to the program time is stored in memory, the starting and ending times of the various programs are in a random order in the memory.
It is likely, in fact, that the broadcast time of the most popular or important programs will be decided early during the program-generation process, with less-important or "filler" programs being decided later, and changed frequently. The problem is exacerbated when many short commercial messages must be interspersed with the main program. Many broadcast stations have random-access automated television tape cartridge players, which can accept instructions, for example from a scheduling computer, to play particular tapes in the system in any order.
In order to automate such a system, the desired identified program selections must be placed in a database, together with their starting and ending times, and frequent comparisons must be made between the current time and the starting and ending time of each program in the database. A conventional computerized scheduling system must either use an indexed database, such as the one described above, or it must sequentially search all the database entries at each time of interest. If there are a large number of entries, the search time may be considerable, and may preempt the operations of the scheduling computer during the comparisons. This preemption can cause delays in implementing last-minute schedule changes since the scheduling computer cannot be used to add information to the database or to review the existing schedule while it is searching for the next scheduled event.
The duration of each search may increase the minimum time increment between adjacent starts and stops. This may be disadvantageous, as some commercial messages may be as short as ten seconds, and they may conceivably have an even shorter duration. It is undesirable to have a minimum time interval or increment in such a control system, because it reduces the flexibility of the system for operators.
Content-addressable memories (CAM) are known to bypass the sequential-access limitations of conventional random-access memories, as described, for example, in the articles Content-Addressable and Associative Memory: Alternatives to the Ubiquitous RAM, by Chisvin et al., published at pp 51-63 of the July, 1989 issue of COMPUTER, published by IEEE, and A General-Purpose CMOS Associative Processor IC and System, by Storman et al., published at pp 68-77 of the December, 1992 issue of IEEE Micro. As pointed out in the Storman et al. article, there are no general-purpose content-addressable memories, because of considerations of word hits and word length. A CAM system adapted for use in the control of video or audio programming is desired.